package algorithm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

public class LeetCode_1047_removeDuplicates {
    public String removeDuplicates(String S) {
        StringBuffer res = new StringBuffer();
        Deque<Character> stack = new LinkedList<Character>();
        int length = S.length();
        for(int i = 0 ; i < length ; i++){
            if(!stack.isEmpty()&& S.charAt(i) == stack.peek()){
                stack.removeFirst();
                continue;
            }
            stack.push(S.charAt(i));
        }
        while (!stack.isEmpty()){
            res.append(stack.getLast());
            stack.removeLast();
        }
        return  res.toString();
    }
    public static void main(String[] args) {
        LeetCode_1047_removeDuplicates leetCode_1047_removeDuplicates = new LeetCode_1047_removeDuplicates();
        String S = "abbaca";
        String res = leetCode_1047_removeDuplicates.removeDuplicates(S);
        System.out.println("res = " + res);
    }
}
